package dp_algorithm.nowcoder.medium;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bruin_du
 * @description 跳石板
 * https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?
 * tpId=85&&tqId=29852&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
 * @date 2022/5/10 15:43
 **/
public class JumpFlagStone {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int m = in.nextInt();
            int[] stepArr = new int[m + 1];
            stepArr[n] = 1;
            //从 n 到 m 个石板逐个进行遍历,把所有可能的步数记录在数组中
            for(int i = n; i <= m;i++){
                //外层循环走到为0
                //说明还没有方案能够达到这里,所以直接往后走一步
                if(stepArr[i] == 0)
                    continue;
                List<Integer> divisorList = new ArrayList<>();
                findDivisor(divisorList,i);
                //内部循环记录当前石板按照约数规则跳到后面石板
                //并在后面的石板上记录步数
                for (int j = 0; j < divisorList.size(); j++) {
                    int tmp = divisorList.get(j);
                    if(i + tmp <= m){
                        if(stepArr[i + tmp] != 0){
                            //动态规划状态方程
                            //如果不为0,说明已经有跳到该石板的方案了
                            //我们需要在当前的步骤和之前的步骤中选出最小的方案
                            stepArr[i + tmp] = Math.min(stepArr[i + tmp],stepArr[i] + 1);
                        }else{
                            //为0,说明还没有跳到这里的方案
                            stepArr[i + tmp] = stepArr[i] + 1;
                        }
                    }
                }
            }
            //如果最终目的地记录的步数为0
            //说明没有方案能够走到这里,直接返回-1
            if(stepArr[m] == 0)
                System.out.println(-1);
            else
                //目的地的步数不为0,说明有可行的方案走到这里
                //但是需要减一,因为用0代表了没有,1代表开始
                System.out.println(stepArr[m] - 1);
        }
    }

    private static void findDivisor(List<Integer> divisorList,int n) {
        for (int i = 2; i <= (int)Math.sqrt(n); i++) {
            if(n % i == 0) {
                divisorList.add(i);
                if (n / i != i)
                    divisorList.add(n / i);
            }
        }
    }
}
